package 题目集.单调栈or队列.单调队列.舍弃可能性;

import org.junit.Test;

/**
 * 给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [xi, yi] ，并且在 1 <= i < j <= points.length 的前提下， xi < xj 总成立。
 * 请你找出 yi + yj + |xi - xj| 的 最大值，其中 |xi - xj| <= k 且 1 <= i < j <= points.length。
 * 题目测试数据保证至少存在一对能够满足 |xi - xj| <= k 的点。
 * https://leetcode.cn/problems/max-value-of-equation/description/
 */
public class 满足不等式的最大值 {
    /**
     * 暴力解：
     *      枚举每个点距离小于k的点，找出最大值
     *      时间复杂度：O(n^2)
     * 单调队列思路：
     *      因为xj>xi，所以我们要求的数，相当于是后面的数+yi-xi，即找出当前位置左侧符合条件的yi-xi的最大值。
     *      如果当前的yi-xi比之前的大，那么之前的就没有用了。
     *      所以我们可以维护一个单调递减的队列，队列中存放的是点的索引。
     */
    public int findMaxValueOfEquation(int[][] points, int k) {
        int n = points.length;
        int[][] deque = new int[n][];   //0位置点的索引，1位置该点yi-xi的值
        int head = 0, tail = 0;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int v = points[i][1] - points[i][0];
            while (head != tail && points[i][0] - points[deque[head][0]][0] > k) //排除掉不符合条件的点
                head++;
            //因为是单调递减，所以剩下的头是符合条件中最大的
            if (head != tail) { //存在符合条件的
                res = Math.max(res, points[i][0] + points[i][1] + deque[head][1]);
            }
            while (head != tail && v > deque[tail - 1][1]) //排除掉左侧比自己小的点
                tail--;
            deque[tail] = new int[]{i, v};
            tail = (tail + 1) % n;
        }
        return res;
    }

    @Test
    public void test() {
        System.out.println(findMaxValueOfEquation(new int[][]{{1, 3}, {2, 0}, {5, 10}, {6, -10}}, 1));
    }
}
